#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0012.py
@time: 2021/9/13 11:28
@desc: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> list:
        if root == None:
            return []
        res = []
        queue = []
        queue.append(root)
        # bfs
        while len(queue)>0:
            node = queue.pop(0)
            res.append(node.val)
            if not node.left==None:
                queue.append(node.left)
            if not node.right==None:
                queue.append(node.right)

        return res

def buildTree()->TreeNode:
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)

    return root

if __name__ == '__main__':
    inp = buildTree()
    s = Solution()
    res = s.levelOrder(inp)
    print(res)